package J3_16;

import java.util.*;

public class test {

    //给你一个字符串 title ，它由单个空格连接一个或多个单词组成，每个单词都只包含英文字母。请你按以下规则将每个单词的首字母 大写 ：
    //
    //如果单词的长度为 1 或者 2 ，所有字母变成小写。
    //否则，将单词首字母大写，剩余字母变成小写。
    //请你返回 大写后 的 title 。
    public String capitalizeTitle(String title) {
        StringBuilder str = new StringBuilder();
        for (String s : title.split(" ")) {
            if (!str.isEmpty()) {
                str.append(" ");
            }
            if (s.length() > 2) {
                str.append(s.substring(0, 1).toUpperCase());
                s = s.substring(1);
            }
            str.append(s.toLowerCase());
        }
        return str.toString();
    }


    //给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。
    //
    //你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
    //
    //以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。
    //
    //注意 返回的结果字符串 可以 含前导零。
    public String maximumOddBinaryNumber(String s) {
        int count1 = -1;
        int count0 = 0;
        for (char ch : s.toCharArray()) {
            if (ch == '1') {
                count1++;
            } else {
                count0++;
            }
        }
        char[] ch = new char[count0 + count1 + 1];
        for (int i = 0; i < count1; i++) {
            ch[i] = '1';
        }
        for (int i = count1; i < count0 + count1; i++) {
            ch[i] = '0';
        }
        ch[count0 + count1] = '1';
        return new String(ch);

    }


    //给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。
    //
    //你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：
    //
    //从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
    //返回你在矩阵中能够 移动 的 最大 次数。
    public static int maxMoves1(int[][] grid) {
        int row = grid.length;
        int low = grid[0].length;
        int[][] dp = new int[row][low];
        for (int i = low - 2; i >= 0; i--) {
            int tmp = 0;
            boolean step = false;
            if (grid[0][i] < grid[0][i + 1]) {
                tmp = dp[0][i + 1];
                step = true;
            } if (grid[0][i] < grid[1][i + 1]) {
                tmp = Math.max(tmp, dp[1][i + 1]);
                step = true;
            }
            if (step) {
                dp[0][i] = tmp + 1;
            } else {
                dp[0][i] = 0;
            }

            for (int j = 1; j < row - 1; j++) {
                tmp = 0;
                step = false;
                if (grid[j][i] < grid[j - 1][i + 1]) {
                    tmp = dp[j - 1][i + 1];
                    step = true;
                } if (grid[j][i] < grid[j][i + 1]) {
                    tmp = Math.max(tmp, dp[j][i + 1]);
                    step = true;
                } if (grid[j][i] < grid[j + 1][i + 1]) {
                    tmp = Math.max(tmp, dp[j + 1][i + 1]);
                    step = true;
                }
                if (step) {
                    dp[j][i] = tmp + 1;
                } else {
                    dp[j][i] = 0;
                }
            }
            tmp = 0;
            step = false;
            if (grid[row - 1][i] < grid[row - 1][i + 1]) {
                tmp = dp[row - 1][i + 1];
                step = true;
            } if (grid[row - 1][i] < grid[row - 2][i + 1]) {
                tmp = Math.max(tmp, dp[row - 2][i + 1]);
                step = true;
            }
            if (step) {
                dp[row - 1][i] = tmp + 1;
            } else {
                dp[row - 1][i] = 0;
            }
        }
        int max = 0;
        for (int i = 0; i < row; i++) {
            max = Math.max(dp[i][0], max);
        }
        return max;
    }
    public static int maxMoves(int[][] grid) {
        int r = grid.length;
        int l = grid[0].length;
        Set<Integer> q = new HashSet<>();
        for (int i = 0; i < r; i++) {
            q.add(i);
        }
        for (int j = 1;j < l; j++) {
            Set<Integer> q2 = new HashSet<>();
            for (int i : q) {
                for (int i2 =i - 1; i2 <=i + 1; i2++) {
                    if (i2 >= 0 && i2 < r && grid[i][j - 1] < grid[i2][j])
                        q2.add(i2);
                }
            }
            q = q2;
            if (q2.isEmpty()) {
                return j - 1;
            }
        }
        return l - 1;
    }


    //给你一个由 不同 正整数组成的数组 nums ，请你返回满足 a * b = c * d 的元组 (a, b, c, d) 的数量。其中 a、b、c 和 d 都是 nums 中的元素，且 a != b != c != d 。
    public int tupleSameProduct(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int key = nums[i] * nums[j];
                map.put(key, map.getOrDefault(key,1) + 1);
            }
        }
        int ans = 0;
        for (Map.Entry<Integer,Integer> set: map.entrySet()) {
            int val = set.getValue();
            ans += val * (val - 1) * 4;
        }
        return ans;
    }


        public static void main(String[] args) {
        int[][] arr = {{  65,   200,  263, 220,  91,  183,    2,  187, 175,  61, 225, 120,  39},
                        {111,   242,  294,  31, 241,   90,  145,   25, 262, 214, 145,  71, 294},
                        {152,    25,  240,  69, 279,  238,  222,    9, 137, 277,   8, 143, 143},
                        {189,    31,   86, 250,  20,   63,  188,  209,  75,  22, 127, 272, 110},
                        {122,    94,  298,  25,  90,  169,   68,    3, 208, 274, 202, 135, 275},
                        {205,    20,  171,  90,  70,  272,  280,  138, 142, 151,  80, 122, 130},
                        {284,   272,  271, 269, 265,  134,  185,  243, 247,  50, 283,  20, 232},
                        {266,   236,  265, 234, 249,   62,   98,  130, 122, 226, 285, 168, 204},
                        {231,   24,   256, 101, 142,   28,  268,   82, 111,  63, 115,  13, 144},
                        {277,   277,   31, 144,  49,  132,   28,  138, 133,  29, 286,  45,  93},
                        {163,   96,    25,   9,   3,  159,  148,   59,  25,  81, 233, 127,  12},
                        {127,    8,    31, 209, 300,  256,   15,   43,  74,  64,  73, 141, 200}};
        int a = maxMoves(arr);
        System.out.println(a);

    }
}
